Основне статистике (збир, производ, просек, минумум, максимум)
Најчешће коришћени итеративни алгоритми служе за израчунавање статистика бројевних серија. На пример, једну такву серију могу чинити бројеви 1, 2, 3, 4 и 5. Најзначајније статистике су:
- збир елемената (збир бројева из примера је 15),
- производ елемената (производ бројева из примера је 120),
- минимум тј. најмањи од свих елемената (миминум бројева из примера је 1),
- максимум тј. највећи од свих елемената (максимум бројева из примера је 5).
Одређивање збира и производа
На примеру четворочлане серије елемената, прикажимо итеративне алгоритме за одређивање збира и производа. Збир четири броја се најједноставније израчунава изразом
broj1 + broj2 + broj3 + broj4што је због леве асоцијативности сабирања (у програмирању) идентично изразу
((broj1 + broj2) + broj3) + broj4Други начин да се израчунавање збира реализује је да се уведе помоћна
променљива zbir која би се увећавала за текући елемент.
zbir = broj1;
zbir = zbir + broj2;
zbir = zbir + broj3;
...За разлику од полазног решења у ком се збир израчунава само помоћу
једног израза, ово решење је итеративно, и резултат се добија
узастопном применом корака истог облика. Истакнимо још једном врло важну
особину итеративних алгоритама, а то је да се током њиховог извршавања
мења вредност неке променљиве (у овом случају то је променљива
zbir).
Уместо да збир иницијализујемо првим елементом, можемо га иницијализовати нулом, а затим увећавати за један по један елемент.
zbir = 0;
zbir = zbir + broj1;
zbir = zbir + broj2;
...Производ се одређује по веома сличном принципу, осим што уместо иницијализације нулом користимо иницијализацију јединицом (као неутралним елементом за множење) и што уместо сабирања користимо множење.
proizvod = 1;
proizvod = proizvod * broj1;
proizvod = proizvod * broj2;
...У задацима је често потребно израчунати просек тј. аритметичку средину серије елемената, која је једнака количнику збира и броја елемената.
Одређивање минимума и максимума
Потпуно аналогно израчунавању збира неколико бројева, може се израчунати минимум, једино што се уместо операције сабирања два броја користи операција одређивања минимума два броја. У сваком кораку се рачуна минимум минимума свих претходних бројева и текућег броја.
Реално је претпоставити да на располагању имамо функцију којом се
израчунава минимум два броја. Таква функција је обично део стандардне
библиотеке, а када није, једноставно се може дефинисати.
У језику Пајтон минимум два броја може се израчунати
библиотечком функцијом min. Минимум
четири броја онда можемо одредити наредним изразом.
min(min(min(broj1, broj2), broj3), broj4)Максимум израчунавамо по потпуно истом принципу, једино што уместо минимума два броја у сваком кораку користимо максимум два броја.
И у случају налажења минимума уместо једног израза можемо дефинисати и итеративни алгоритам.
minimum = broj1
minimum = min(minimum, broj2)
minimum = min(minimum, broj3)
...Ако би се уместо функције за рачунање минимума два броја употребило гранање (овај пут изражено условним изразом), дошло би се до следећег кода.
minimum = broj1
minimum = broj2 if broj2 < minimum else minimum
minimum = broj3 if broj3 < minimum else minimum
...Ако би се уместо условног израза користила наредба гранања, добио би се следећи облик кода.
minimum = broj1
if broj2 < minimum:
minimum = broj2
else:
minimum = minimum
if broj3 < minimum:
minimum = broj3
else:
minimum = minimum
...Јасно је да гране else немају никакав ефекат и могу се
изоставити. Тиме добијамо уобичајени алгоритам одређивања минимума.
minimum = broj1
if broj2 < minimum:
minimum = broj2
if broj3 < minimum:
minimum = broj3
...Дакле, променљиву minimum иницијализујемо вредношћу
првог броја, а затим је редом поредимо са другим, трећим, четвртим и
петим бројем и када год је неки од тих бројева мањи од дотадашње
вредности минимума тј. вредности променљиве minimum,
ажурирмо вредност те променљиве и постављамо је на број за који смо
открили да је мањи од ње.
Можемо и мало прецизније да анализирамо претходни кôд и да докажемо
његову коректност. У првом кораку вредност променљиве
minimum биће минимум једночланог скупа
{broj1}, у другом биће минимум двочланог скупа
{broj1, broj2}, након трећег биће минимум скупа
{broj1, broj2, broj3} и тако даље. Такав услов, дакле, важи
у сваком кораку нашег програма и назива се инваријанта. Ако је,
на пример, вредност променљиве minumum вредност минимума
скупа {broj1, broj2, broj3} и ако је broj4
мањи од вредности те променљиве, тада је broj4 мањи од
најмање вредности у скупу {broj1, broj2, broj3}, што значи
да је мањи од свих вредности тог скупа и да је минимум скупа
{broj1, broj2, broj3, broj4} управо broj4.
Пошто се вредност променљиве minimum ажурира на вредност
broj4 одржава се услов да је вредност променљиве
minimum управо минимум скупа
{broj1, broj2, broj3, broj4}, тј. инваријанта је одржана.
Са друге стране, ако услов не важи, то значи да је најмањи од бројева из
скупа {broj1, broj2, broj3} мањи или једнак вредности
broj4 и то је уједно минимум скупа
{broj1, broj2, broj3, broj4}. Пошто се вредност променљиве
minimum не мења, инваријанта је опет одржана.
Као што се збир може иницијализовати нулом, а производ јединицом, што
су неутралне вредности за сабирање тј. множење, тако се и минимум може
иницијализовати вредношћу \(+\infty\),
а максимум вредношћу \(-\infty\).
У програмском језику Пајтон целобројни тип је
неограничен, међутим, већина задатака у збирци је таква да се може
радити и у другим језицима у којима постоје ограничења вредности
целобројних типова. У језику Пајтон уместо вредности \(+\infty\) можемо употребити вредност
sys.maxsize (која је обично једнака \(2^{63}-1\)), јер су задаци такви да се у
њима не јављају бројеви већи од тога. Слично, уместо вредности \(-\infty\) се може користити
-sys.maxsize-1 (која је обично једнака \(-2^{63}\)), јер је то најмањи број који се
у другим језицима може представити уграђеним целобројним типовима
података.
Рецимо и да се понављање кода може избећи ако би се употребила петља, што ћемо примењивати када будемо радили са дужим серијама елемената. Сви принципи алгоритма су исти и зато рад са малим серијама бројева представља одличан увод за рад са дужим серијама и петљама.
Низови и библиотечке функције
Уместо ручне имплементације одређивања минимума четири променљиве, можемо употребити низ и библиотечке функције за одређивање максимума низа. О разним врстама низова биће речи у поглављу о низовима, а до тада ћемо разматрати само низове који садрже мали број елемената и који су иницијализовани директним набрајањем њихових елемената.
У језику Пајтон низ који садржи пет бројева се може дефинисати на следећи начин.
a = [broj1, broj2, broj3, broj4, broj5]Овакав низ се у Пајтону зове листа, а приликом набрајања елемената они се наводе у угластим заградаима. Могуће је у старту формирати празну листу, а касније додавати један по један елемент на ту листу.
a = []
a.append(int(input()))
a.append(int(input()))
...Приметимо да бројање позиција елемената низа почиње увек од нуле!
Када је низ дефинисан, број, збир, минимум и максимум његових
елемената можемо веома једноставно да одредимо редом помоћу функција
len, sum, min и max
које су уграђене у сам језик Пајтон.
...
n = len(a) # odredjuje broj elemenata niza a
zbir = sum(a) # odredjuje zbir svih elemenata niza a
minimum = min(a) # odredjuje minimum svih elemenata niza a
maksimum = max(a) # odredjuje maksimum svih elemenata niza aУ Пајтону функцијама min и max можемо да
проследимо додатни параметар key=f, где је f
нека функција. Код тако задатог позива функције min, не
тражимо елемент x низа a који је најмањи, него
онај за који је f(x) најмање. Слично важи и за функцију
max.